package main.堆;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author tmh
 * @date 2024/7/23 20:35
 * @description
 */
public class T215数组中的第K个最大元素 {
    public int findKthLargest(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        return quickSort(list, k);
    }

    /**
     * 使用快速排序
     */
    private int quickSort(List<Integer> nums, int k) {
        //随机选择pivot
        Random random = new Random();
        //这里使用nums里面元素来当基准元素
        int pivot = nums.get(random.nextInt(nums.size()));
        List<Integer> big = new ArrayList<>();
        List<Integer> equals = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        for (int num : nums) {
            if (num > pivot) {
                big.add(num);
            } else if (num == pivot) {
                equals.add(num);
            } else {
                small.add(num);
            }
        }
        //开始递归 每个判断里面要直接return
        if (k <= big.size()) {
            return quickSort(big, k);
        }
        //第k大的元素在small中，递归划分
        //这里要记下small这个判断的条件
        if (nums.size() - small.size() < k) {
            return quickSort(small, k - nums.size() + small.size());
        }
        return pivot;
    }
}